Міністерство Освіти та Науки України Національний університет “Львівська політехніка” Кафедра ІСМ
Лабораторна робота №7 На тему: Код Хемінга З курсу: “Комп’ютерні мережі” Виконав: Ст.гр. КН-3 Львів 2008 Метою роботи: Вивчення будови одного з найпростіших систематичних кодів - коду Хемінга, та дослідження його коректуючих властивостей. В процесі автоматизованого управліня технікою, виробничими процесами, галузями народного господарства, а також в процесах творчоі діяльност1 людини відбуваеться інтенсивний обмін інформаціею між окремими ланками систем управліня, між людиною та технікою, людиною та природою, між окремими людьми. Bci ці процеси повязані з отриманням, передачею, перетворенням, накопиченням збереженням та відображенням інформаці. Структурна схема інформаційноії системи наведена на рис.1. Рис.1. Структурна схема іформаційної системи. Повідомлення, для передачі його по ідповідній адресі повинно бути спечатку перетворено у сигнал. По кодуванням в широкому розумжні цього слова розуміють процес перетворення поідомлень у сигнал. Завадостійкі ходи - один з найбільш ефективних зacoбiв забезпечення високоі достовірності передачі дискретноі інформації. Завадостійкі коди - це ходи, які дозволяють викривати та виправляти помилки, які виникають через дію завад. Завадостійкість кодування забезпечуеться за рахунок введения надлишковості в код; комбшації, тобто за рахунок того, що не ва символи в кодових хомбшаціях викрристовуються для передачіінформації повідомлення. Одним з параметрів, що характеризує ступінь надлишковості ходу є кодова відстань. Кодова відстань - це мінімальна кількість одиниць в сумі двох довільних кодових комбінацій коду. Кодова відстань, таким чином описує мінімальну розбіжність двох кодових хомбінацій. Bci завадостійкі коди можна поділити на два основних класи: блочні та неперервні. В блочних кодах кожному повідомленню (або його елементу) ставиться у відповідність кодова комбінація (блок) з певноі кількості символів. Блоки кодуються та декодуються незалежно один від другого. На сьогоднішнйй день найбільш широкий клас коректуючих кодів складають систематичні коди. Ці коди відносяться до груп блочних кодів. Для систематичного коду сума по модулю два, двох дозволених ходових комбінащй також дає дозволену кодову комбінацію. Одним з систематичних кодів є код Хемінга. Відомо кілька різновидів коду Хемінга, які характеризуються різними коректуючими зластивостями. До цих кодів звичайно відносять коди з виправленням однократних помилок та виявленням двохкратних помилок. Код Хемінга, який забезпечує виправлення вcix однократних помилок мусить мати мінімальну кодову відстань: D min=3 Довжина ходу n вибираеться виходячи з такоі умови: 2^k<=2^n/(1+n) де k - кількість інформащійних символів. Код будуеться таким чином, щоб в результаті r = п * k nepedipor отримати r - розрядне двійкове число, яке вказуе на номер спотвореного символа в кодоdsq комбінаці. Для цього перевірочні символи повинні знаходитися в номерах лозицій, що виражаються ступенем двійки так як кожний з них входить в одно перевірочне рівняння. Таким чином, якщо нумерувати позиції зліва направо, то контрольні символи повинні знаходитися, в першій, другій, четверті позиціях. Наприклад, розташування символів в коді Хемінга з п = 9 буде таким: а(1) а(2) а(3) а(4) а(5) а(6) а(7) а(8) а(9) r(1) r(2) k(1) r(3) k(2) k(3) k(4) r(4) k(5) Результат першоі перевірки- дає цифру молодшого розряду синдрому в двійковому записі. Якщо результат такоі перевірки 1, то один з символів групи, що перевіряеться спотворено. Таким, чином, першою перевіркою повинні бути охоплені символи з номерами, які маютять в двіковому запису одиниці в першому розряді: 1, 3, 5, 7, 9 i т. д. Результат другоі перевірки дає цифру другого розряду синдрому. Тому, другою перевіркою треба охопити символи з номерами, як( містять в двійковій формі запису одиницю в другому розряді : 2, 3, 6, 7, 10 i т. д. Аналогіч...